#include <iostream>
#include <stack>
using namespace std;
typedef struct Tnode
{
    int data;
    struct Tnode* left;
    struct Tnode* right;
}Tnode;
void createTree(Tnode* &root)
{
    int node;
    cin>>node;
    if(node==-1)
    {
      return ;
    }
    Tnode* temp=new Tnode;
    temp->data=node;
    temp->left=NULL;
    temp->right=NULL;
    root=temp;
    createTree(root->left);
    createTree(root->right);

}
void Postorder_norecur(Tnode* root)
{
    Tnode* p=root;
    Tnode* l=NULL;//指向上一次打印的节点
    stack<Tnode* >s;
    while(!s.empty()||p)
    {
        while(p)
        {
            s.push(p);
            p=p->left;
        }
        //没有左孩子了 就出栈
        Tnode* top=s.top();
        if(top->right==NULL||top->right==l)
        {
            cout<<top->data<<" ";
            l=top;
            s.pop();
        } else
        {
            p=top->right;
        }

    }
}
void inorder_norecur(Tnode* root)
{
    Tnode* p=root;
    stack<Tnode*>s;
    while(!s.empty()||p)
    {
        while(p)
        {
            s.push(p);
            p=p->left;
        }
        Tnode* top=s.top();
        s.pop();
        cout<<top->data<<" ";
        p=top->right;
    }
}

void preorder_norecur(Tnode* root)
{
    Tnode* p=root;
    stack<Tnode*>s;
    while(!s.empty()||p)
    {
        while(p)
        {
            cout<<p->data<<" ";
            s.push(p);
            p=p->left;
        }
        Tnode* top=s.top();
        p=top->right;
        s.pop();
    }
}
int main() {
    Tnode* root=NULL;
    createTree(root);
//    Postorder_norecur(root);
//    inorder_norecur(root);
//     preorder_norecur(root);


    return 0;
}
